import Comparator from '../../utils/comparator/Comparator.js';

export default class DoublyLinkedList {
  /**
   * 双向链表的构造函数
   * @param {Function} [comparatorFunction] - 用于比较节点值的函数
   */
  constructor(comparatorFunction) {
    // 头节点初始化为null
    this.head = null;

    // 尾节点初始化为null
    this.tail = null;

    // 初始化比较器
    this.compare = new Comparator(comparatorFunction);
  }

  /**
   * 在链表头部插入一个新节点
   * @param {*} value - 要插入节点的值
   * @return {DoublyLinkedList} - 插入新节点后的链表
   */
  prepend(value) {
    // 创建一个新节点，并将其设为头节点
    const newNode = new DoublyLinkedListNode(value, this.head);

    // 如果存在头节点，则更新其前一个节点引用为新节点
    if (this.head) {
      this.head.previous = newNode;
    }
    this.head = newNode;

    // 如果尾节点为空，则将新节点设为尾节点
    if (!this.tail) {
      this.tail = newNode;
    }

    return this;
  }

  /**
   * 在链表尾部插入一个新节点
   * @param {*} value - 要插入节点的值
   * @return {DoublyLinkedList} - 插入新节点后的链表
   */
  append(value) {
    // 创建一个新节点
    const newNode = new DoublyLinkedListNode(value);

    // 如果链表为空，则将新节点设为头节点和尾节点
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return this;
    }

    // 将新节点附加到链表尾部
    this.tail.next = newNode;
    newNode.previous = this.tail;
    this.tail = newNode;

    return this;
  }


  /**
   * 删除链表中具有给定值的节点
   * @param {*} value - 要删除节点的值
   * @return {DoublyLinkedListNode} - 删除的节点
   */
  delete(value) {
    // 如果链表为空，则直接返回null
    if (!this.head) {
      return null;
    }

    let deletedNode = null;
    let currentNode = this.head;

    // 遍历链表，寻找要删除的节点
    while (currentNode) {
      if (this.compare.equal(currentNode.value, value)) {
        deletedNode = currentNode;

        // 如果要删除的是头节点，则更新头节点
        if (deletedNode === this.head) {
          this.head = deletedNode.next;
          if (this.head) {
            this.head.previous = null;
          }
          if (deletedNode === this.tail) {
            this.tail = null;
          }
          // 如果要删除的是尾节点，则更新尾节点
        } else if (deletedNode === this.tail) {
          this.tail = deletedNode.previous;
          this.tail.next = null;
        } else {
          // 如果要删除的是中间节点，则调整相邻节点的引用
          const previousNode = deletedNode.previous;
          const nextNode = deletedNode.next;
          previousNode.next = nextNode;
          nextNode.previous = previousNode;
        }
      }
      currentNode = currentNode.next;
    }

    return deletedNode;
  }

  /**
   * 在链表中查找具有给定值或满足回调函数的节点
   * @param {Object} findParams - 查找参数对象
   * @param {*} findParams.value - 要查找的节点值
   * @param {function} [findParams.callback] - 查找的回调函数
   * @return {DoublyLinkedListNode} - 找到的节点
   */
  find({ value = undefined, callback = undefined }) {
    // 如果链表为空，则直接返回null
    if (!this.head) {
      return null;
    }

    let currentNode = this.head;

    // 遍历链表，查找符合条件的节点
    while (currentNode) {
      if (callback && callback(currentNode.value)) {
        return currentNode;
      }
      if (value !== undefined && this.compare.equal(currentNode.value, value)) {
        return currentNode;
      }
      currentNode = currentNode.next;
    }

    return null;
  }

  /**
   * 删除并返回链表的尾节点
   * @return {DoublyLinkedListNode} - 删除的尾节点
   */
  deleteTail() {
    // 如果链表为空，则直接返回null
    if (!this.tail) {
      return null;
    }

    // 如果链表只有一个节点，则将头尾节点置为null
    if (this.head === this.tail) {
      const deletedTail = this.tail;
      this.head = null;
      this.tail = null;
      return deletedTail;
    }

    // 将倒数第二个节点设为新的尾节点，并将其下一个节点引用置为null
    const deletedTail = this.tail;
    this.tail = this.tail.previous;
    this.tail.next = null;

    return deletedTail;
  }

  /**
   * 删除并返回链表的头节点
   * @return {DoublyLinkedListNode} - 删除的头节点
   */
  deleteHead() {
    // 如果链表为空，则直接返回null
    if (!this.head) {
      return null;
    }

    const deletedHead = this.head;

    // 如果链表只有一个节点，则将头尾节点置为null
    if (this.head.next) {
      this.head = this.head.next;
      this.head.previous = null;
    } else {
      this.head = null;
      this.tail = null;
    }

    return deletedHead;
  }

  /**
   * 将链表转换为数组
   * @return {DoublyLinkedListNode[]} - 转换后的数组
   */
  toArray() {
    const nodes = [];

    // 遍历链表，将节点添加到数组中
    let currentNode = this.head;
    while (currentNode) {
      nodes.push(currentNode);
      currentNode = currentNode.next;
    }

    return nodes;
  }

  /**
   * 根据给定的数组创建链表
   * @param {*[]} values - 要转换为链表的数组
   * @return {DoublyLinkedList} - 创建后的链表
   */
  fromArray(values) {
    // 遍历数组，将每个元素附加到链表尾部
    values.forEach((value) => this.append(value));

    return this;
  }

  /**
   * 将链表转换为字符串表示形式
   * @param {function} [callback] - 可选的回调函数，用于自定义节点的字符串表示
   * @return {string} - 转换后的字符串
   */
  toString(callback) {
    // 将链表转换为数组，并使用回调函数处理每个节点的字符串表示
    return this.toArray().map((node) => node.toString(callback)).toString();
  }

  /**
   * Reverse a linked list. 反转链表
   * @returns {DoublyLinkedList} - 反转后的链表
   */
  reverse() {
    // 初始化指针，用于遍历链表
    let currNode = this.head;
    let prevNode = null;
    let nextNode = null;

    // 遍历链表，反转节点的next和previous指针
    while (currNode) {
      // Store next node.
      nextNode = currNode.next;
      prevNode = currNode.previous;

      // Change next node of the current node so it would link to previous node.
      currNode.next = prevNode;
      currNode.previous = nextNode;

      // Move prevNode and currNode nodes one step forward.
      prevNode = currNode;
      currNode = nextNode;
    }

    // Reset head and tail. 重新设置头尾节点
    this.tail = this.head;
    this.head = prevNode;

    return this;
  }

}
